<header>
    动态规划
</header>
<p>
    基本的思想也是将待解问题分解称若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
</p>
<p>
    但与分治法不同的是，子问题往往不是互相独立的，可能存在需要重复求解的子问题，这点非常重要。由此，我们在求解一个子问题的时候会记录其解，下次遇到类似的问题，先去查一下表，如果已经有了解，直接使用，否则再计算后进行登记。
</p>
<p>
    通常可以按以下步骤设计算法：
</p>
<ol>
    <li>
        找出最优解的性质，并刻画其结构性质。
    </li>
    <li>
        递归地定义最优值。
    </li>
    <li>
        以自底向上的方式计算出最优值。
    </li>
    <li>
        根据计算最优值时得到的信息，构造最优解。
    </li>
</ol>
<p>
    可以看出来，求解的规模是从小到大进行的，这意味着所有的子问题都会被求解一遍。而在有时候，比如我们可能只是需要一个解，那也可以考虑从大到小进行，也就是
    <span class="important">备忘录算法</span>
    。
</p>
<p>
    一般来说，如果一个问题的所有子问题都至少要解一次时，用动态规划比备忘录要好，因为此时动态规划没有任何多余的计算。当子问题中部分可不必求解时，用备忘录则更好。
</p>